package linkList;

public class N148_SortLinkedList {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = sortList(slow.next);
        slow.next = null;
        ListNode left = sortList(head);
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode vnode = new ListNode(0);
        ListNode tmp = vnode, t1 = l1, t2 = l2;
        while (t1 != null && t2 != null) {
            if (t1.val <= t2.val) {
                tmp.next = t1;
                t1 = t1.next;
            } else {
                tmp.next = t2;
                t2 = t2.next;
            }
            tmp = tmp.next;
        }
        if (t1 != null) tmp.next = t1;
        if (t2 != null) tmp.next = t2;
        return vnode.next;
    }


}
